package com.ryujung.binary_tree.leetCode_106;


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ",\n left=" + left +
                ",\n right=" + right +
                '}';
    }
}

class Solution {

    /**
     * 思路：
     * 中序：左子树、根节点、右子树
     * 后续：左子树、右子树、根节点
     * 根据后序确定根节点，再根据中序确定左子树和右子树
     * 然后在子树和递归进行判断
     * <p>
     * 当子树为空，构建并返回当前节点
     */
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder, postorder, 0, inorder.length - 1, postorder.length - 1);
    }

    /**
     * left和right是中序遍历中，需要构建TreeNode的左右边界，tail是当前需要构建的node的后续遍历的根节点位置
     * 难点：
     * 如何确定左子树的根节点位置和右子树的根节点，在后序遍历中的位置
     * 左子树：当前的tail减去右子树的总长度，再减1  右子树长度 = right - mid
     * 右子树：right - 1
     */
    private static TreeNode helper(int[] inorder, int[] postorder, int left, int right, int tail) {
        if (left > right) return null;

        TreeNode root = new TreeNode(postorder[tail]);
        int midIndex = left;
        for (int i = left; i <= right; i++) {
            if (inorder[i] == postorder[tail]) {
                midIndex = i;
                break;
            }
        }

        root.left = helper(inorder, postorder, left, midIndex - 1, tail - (right - midIndex) - 1);
        root.right = helper(inorder, postorder, midIndex + 1, right, tail - 1);

        return root;
    }

    public static void main(String[] args) {
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        int[] postorder = new int[]{9, 15, 7, 20, 3};
        TreeNode result = buildTree(inorder, postorder);
        System.out.println(result);
    }
}